home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / prgtools / gnustuff / minix / libsrc~1.z / libsrc~1 / malloc.c < prev    next >
Encoding:
C/C++ Source or Header  |  1989-12-28  |  5.5 KB  |  246 lines
  1. #include "lib.h"
  2. #include <memory.h>
  3.  
  4. # define _LMALLOC  lmalloc
  5. # define _LREALLOC lrealloc
  6. # define _LCALLOC  lcalloc
  7.  
  8.  
  9. /* replace undef by define */
  10. #undef     DEBUG        /* check assertions */
  11. #undef     SLOWDEBUG    /* some extra test loops (requires DEBUG) */
  12.  
  13. #ifdef DEBUG
  14. #define    ASSERT(b)    if (!(b)) assert_failed();
  15. #else
  16. #define    ASSERT(b)    /* empty */
  17. #endif
  18.  
  19. #ifdef i8088
  20. #define    ptrint        int
  21. #endif
  22. #ifdef ATARI_ST
  23. #define    ptrint        long
  24. #endif
  25.  
  26. #define BRKSIZE        ((unsigned long)1024)
  27. #define    PTRSIZE        (sizeof(char *))
  28.  
  29. #ifdef __GNUC__
  30. #define Align(x,a)    (( ((ptrint)(x)) + ((ptrint)a - 1L)) & ~((ptrint)a - 1L))
  31. #else
  32. #define Align(x,a)    (((x) + (a - 1)) & ~(a - 1))
  33. #endif
  34.  
  35. #define NextSlot(p)    (* (char **) ((p) - PTRSIZE))
  36. #define NextFree(p)    (* (char **) (p))
  37.  
  38. /*
  39.  * A short explanation of the data structure and algorithms.
  40.  * An area returned by malloc() is called a slot. Each slot
  41.  * contains the number of bytes requested, but preceeded by
  42.  * an extra pointer to the next the slot in memory.
  43.  * '_bottom' and '_top' point to the first/last slot.
  44.  * More memory is asked for using brk() and appended to _top.
  45.  * The list of free slots is maintained to keep malloc() fast.
  46.  * '_empty' points the the first free slot. Free slots are
  47.  * linked together by a pointer at the start of the
  48.  * user visable part, so just after the next-slot pointer.
  49.  * Free slots are merged together by free().
  50.  */
  51.  
  52. #ifndef __STDC__    /* for __STDC__ pick up proto from <std.h> */
  53. extern _VOIDSTAR sbrk();
  54. extern _VOIDSTAR brk();
  55. #endif
  56. static char *_bottom, *_top, *_empty;
  57.  
  58. static int grow(len)
  59. unsigned long len;
  60. {
  61.   register char *p;
  62.  
  63.   ASSERT(NextSlot(_top) == 0);
  64.   p = (char *) Align((ptrint)_top + len, BRKSIZE);
  65.   if (p < _top || brk(p) != 0)
  66.     return(0);
  67.   NextSlot(_top) = p;
  68.   NextSlot(p) = 0;
  69.   free(_top);
  70.   _top = p;
  71.   return(1);
  72. }
  73.  
  74. #ifndef __MSHORT__
  75. asm(".text; .even; .globl _malloc; _malloc:"); /* dept of dirty tricks */
  76. #endif
  77. _VOIDSTAR _LMALLOC (size)
  78. unsigned long size;
  79. {
  80.   register char *prev, *p, *next, *new;
  81.   register unsigned long len;
  82.   register short ntries;
  83.  
  84.   if (size == 0)
  85.     size = PTRSIZE;        /* avoid slots less that 2*PTRSIZE */
  86.   for (ntries = 0; ntries < 2; ntries++) {
  87.     len = Align(size, PTRSIZE) + PTRSIZE;
  88.     if (_bottom == 0) {
  89.         p = sbrk((int)(2 * (int)PTRSIZE));
  90.         p = (char *) Align((ptrint)p, PTRSIZE);
  91.         p += PTRSIZE;
  92.         _top = _bottom = p;
  93.         NextSlot(p) = 0;
  94.     }
  95. #ifdef SLOWDEBUG
  96.     for (p = _bottom; (next = NextSlot(p)) != 0; p = next)
  97.         ASSERT(next > p);
  98.     ASSERT(p == _top);
  99. #endif
  100.     for (prev = 0, p = _empty; p != 0; prev = p, p = NextFree(p)) {
  101.         next = NextSlot(p);
  102.         new = p + len;
  103.         if (new > next)
  104.             continue;        /* too small */
  105.         if (new + PTRSIZE < next) {    /* too big, so split */
  106.             /* + PTRSIZE avoids tiny slots on free list */
  107.             NextSlot(new) = next;
  108.             NextSlot(p) = new;
  109.             NextFree(new) = NextFree(p);
  110.             NextFree(p) = new;
  111.         }
  112.         if (p < _bottom)
  113.             return(0);
  114.         if (prev)
  115.             NextFree(prev) = NextFree(p);
  116.         else
  117.             _empty = NextFree(p);
  118.         return(p);
  119.     }
  120.     if (grow(len) == 0)
  121.         break;
  122.   }
  123.   ASSERT(ntries != 2);
  124.   return(0);
  125. }
  126.  
  127. #ifndef __MSHORT__
  128. asm(".text; .even; .globl _realloc; _realloc:"); /* dept of dirty tricks */
  129. #endif
  130. _VOIDSTAR _LREALLOC(old, size)
  131. _VOIDSTAR old;
  132. unsigned long size;
  133. {
  134.   register char *prev, *p, *next, *new;
  135.   register unsigned long len, n;
  136.  
  137.   if(old == (_VOIDSTAR)0) return _LMALLOC(size);
  138.  
  139.   len = Align(size, PTRSIZE) + PTRSIZE;
  140.   next = NextSlot(old);
  141.   n = (unsigned long)(next - (char *)old);            /* old length */
  142.   /*
  143.    * extend old if there is any free space just behind it
  144.    */
  145.   for (prev = 0, p = _empty; p != 0; prev = p, p = NextFree(p)) {
  146.     if (p > next)
  147.         break;
  148.     if (p == next) {    /* 'next' is a free slot: merge */
  149.         NextSlot(old) = NextSlot(p);
  150.         if (prev)
  151.             NextFree(prev) = NextFree(p);
  152.         else
  153.             _empty = NextFree(p);
  154.         next = NextSlot(old);
  155.         break;
  156.     }
  157.   }
  158.   new = old + len;
  159.   /*
  160.    * Can we use the old, possibly extended slot?
  161.    */
  162.   if (new <= next) {                /* it does fit */
  163.     if (new + PTRSIZE < next) {        /* too big, so split */
  164.         /* + PTRSIZE avoids tiny slots on free list */
  165.         NextSlot(new) = next;
  166.         NextSlot(old) = new;
  167.         free(new);
  168.     }
  169.     return(old);
  170.   }
  171.   if ((new = _LMALLOC(size)) == 0)        /* it didn't fit */
  172.     return(0);
  173.   bcopy(old, new, (long)n);                /* n < size */
  174.   free(old);
  175.   return(new);
  176. }
  177.  
  178. #ifndef __MSHORT__
  179. asm(".text; .even; .globl _calloc; _calloc:"); /* dept of dirty tricks */
  180. #endif
  181. _VOIDSTAR _LCALLOC(n, size)
  182. unsigned long n, size;
  183. {
  184.   register char *cp;
  185.  
  186.   n *= size;
  187.   cp = _LMALLOC(n);
  188.   if (cp == (char *)0)
  189.     return ((char *)0);
  190.   bzero(cp, (long)n);
  191.   return(cp);
  192. }
  193.  
  194. void free(p)
  195. _VOIDSTAR p;
  196. {
  197.   register char *prev, *next;
  198.  
  199.   ASSERT(NextSlot(p) > p);
  200.   for (prev = 0, next = _empty; next != 0; prev = next, next = NextFree(next))
  201.     if ((char *)p < next)
  202.         break;
  203.   NextFree(p) = next;
  204.   if (prev)
  205.     NextFree(prev) = p;
  206.   else
  207.     _empty = p;
  208.   if (next) {
  209.     ASSERT(NextSlot(p) <= next);
  210.     if (NextSlot(p) == next) {        /* merge p and next */
  211.         NextSlot(p) = NextSlot(next);
  212.         NextFree(p) = NextFree(next);
  213.     }
  214.   }
  215.   if (prev) {
  216.     ASSERT(NextSlot(prev) <= p);
  217.     if (NextSlot(prev) == p) {        /* merge prev and p */
  218.         NextSlot(prev) = NextSlot(p);
  219.         NextFree(prev) = NextFree(p);
  220.     }
  221.   }
  222. }
  223.  
  224. #ifdef DEBUG
  225. static assert_failed()
  226. {
  227.     write(2, "assert failed in lib/malloc.c\n", 30);
  228.     abort();
  229. }
  230. #endif
  231.  
  232. #ifdef __MSHORT__
  233. _VOIDSTAR malloc(n)
  234. unsigned int n;
  235. { return lmalloc((unsigned long)n); }
  236.  
  237. _VOIDSTAR realloc(old, n)
  238. _VOIDSTAR old;
  239. unsigned int n;
  240. { return lrealloc(old, (unsigned long)n); }
  241.  
  242. _VOIDSTAR calloc(n, m)
  243. unsigned int n, m;
  244. { return lcalloc((unsigned long)n, (unsigned long)m); }
  245. #endif
  246.